| 翻訳と辞書 |
| greedy coloring ： ウィキペディア英語版 |
greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings do not in general use the minimum number of colors possible. However, they have been used in mathematics as a technique for proving other results about colorings and in computer science as a heuristic to find colorings with few colors.
==Greed is not always good==
A crown graph (a complete bipartite graph ''K''''n'',''n'', with the edges of a perfect matching removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use ''n'' colors, while the optimal number of colors for this graph is two. There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum.〔.〕 Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.
It is NP-complete to determine, for a given graph ''G'' and number ''k'', whether there exists an ordering of the vertices of ''G'' that forces the greedy algorithm to use ''k'' or more colors. In particular, this means that it is difficult to find the worst ordering for ''G''.〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「greedy coloring」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|